package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/11/30 21:40
 */
public class AC839模拟堆 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        PriorityQueue priorityQueue = new PriorityQueue();
        int n = Integer.parseInt(s[0]);
        while (n-- > 0) {
            s = reader.readLine().split(" ");
            if ("I".equals(s[0])) {
                int x = Integer.parseInt(s[1]);
                priorityQueue.add(x);
            } else if ("PM".equals(s[0])) {
                writer.write(priorityQueue.peek() + "\n");
                writer.flush();
            } else if ("DM".equals(s[0])) {
                priorityQueue.poll();
            } else if ("D".equals(s[0])) {
                int k = Integer.parseInt(s[1]);
                priorityQueue.removeKthElement(k);
            } else if ("C".equals(s[0])) {
                int k = Integer.parseInt(s[1]), x = Integer.parseInt(s[2]);
                priorityQueue.updateKthElement(k, x);
            }
        }
        writer.flush();
    }

    private static class PriorityQueue {
        private int[] element = new int[100];
        private int size = 0;

        //这题需要维护两个数组；pointToHeap[i]：第i个插入的数在堆中的下标；heapToPoint[i]：堆元素element[i]是第几个插入的元素
        private int[] pointToHeap = new int[100];
        private int[] heapToPoint = new int[100];
        private int m = 0;

        private void swim(int k) {
            //第k个元素上浮
            int cur = k, parentIndex = k >> 1;
            while (cur > 1 && element[cur] < element[parentIndex]) {
                swap(cur, parentIndex);
                cur = parentIndex;
                parentIndex >>= 1;
            }
        }

        private void sink(int k) {
            //第k个元素下沉
            int cur = k;
            while (cur * 2 <= size) {
                int left = cur * 2, right = cur * 2 + 1;
                if (element[left] < element[cur] || (right <= size && element[right] < element[cur])) {
                    int child = left;
                    if (right <= size && element[right] < element[left]) child = right;
                    swap(cur, child);
                    cur = child;
                } else {
                    break;
                }
            }
        }

        public void add(int x) {
            element[++size] = x;

            //记录当前插入元素在堆中的下标，和堆中元素是第几个插入的
            pointToHeap[++m] = size;
            heapToPoint[size] = m;

            swim(size);
        }

        public int poll() {
            int removeElement = peek();
            swap(1, size--);
            sink(1);
            return removeElement;
        }

        public int peek() {
            return element[1];
        }

        //删除第k个插入的元素，本题特有方法
        public void removeKthElement(int k) {
            //找到第k个插入元素在堆中的下标
            k = pointToHeap[k];
            swap(k, size--);
            //会自动选择上浮还是下沉
            swim(k);
            sink(k);
        }

        //修改第k个插入元素为x，本题特有方法
        public void updateKthElement(int k, int x) {
            k = pointToHeap[k];
            element[k] = x;
            swim(k);
            sink(k);
        }

        private void swap(int i, int j) {
            //交换堆中元素element[i]和element[j]的值
            int t = element[i];
            element[i] = element[j];
            element[j] = t;

            //交换 pointToHeap[heapToPoint[i]] 和 pointToHeap[heapToPoint[j]]
            t = pointToHeap[heapToPoint[i]];
            pointToHeap[heapToPoint[i]] = pointToHeap[heapToPoint[j]];
            pointToHeap[heapToPoint[j]] = t;

            //交换 heapToPoint[i] 和 heapToPoint[j]
            t = heapToPoint[i];
            heapToPoint[i] = heapToPoint[j];
            heapToPoint[j] = t;
        }
    }
}
